Multiprocessor systems which service a multitude of requests (e.g., queries) from a large number of users must use their resources efficiently in order to service the requests without undue delay. This is especially true for web servers which receive queries for service from multiple users simultaneously. Queries from users may be for a particular web page or for a set of search results, in the case where the server is a web crawler server. If there is undue delay in servicing the requests, the users may discontinue use of the web server.
In a multiprocessor system, load balancing is required to distribute received queries among a plurality of processors to allow efficient servicing of the queries or other requests. If some processors are heavily loaded with queries while other processors are lightly loaded or remain unused for periods of time, the average time required to service a query can rise considerably.
Prior load balancers known in the art have managed distribution of requests or queries in a round robin basis or have directed requests to the processor with the lowest load for servicing. The round robin method, however, does not take into account possible variations in processor load capacity or processing power among the plurality of processors in the system. Therefore, over time, processors with a lower load capacity would be heavily loaded while processors with a higher load capacity would be lightly loaded or remain unused for periods of time.
The method of directing requests for service to the processor with the lowest load also has a drawback in that once the processor with the lowest load is identified, it will draw the most traffic, an effect known as herding.
Another method of request distribution is to randomly select a set of processors and assign the request to the processor in this set with lowest associated load for servicing. However, this approach does not take into account that there may be a preferred choice of processors and this method can expend valuable resources by querying and comparing load values of several processors. See for example U.S. Pat. No. 5,991,808.
Various load balancing methods have been used in multiprocessor systems. However, there remains a need for a simple and efficient method for balancing the load distributions of a multiprocessor system which does not unduly expend valuable system resources.